package linklist;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-04
 * Time: 17:27
 */



public class MyLinkList {


    public int data;
    public MyLinkList.Node next;

    //静态内部类
     public static class Node {
        public int data;//0
        public Node next;//引用类型默认值为NULL

        public Node(int data) {
            this.data = data;

        }
    }

    /**保存整个没有（哨兵位）单链表头节点的引用
     *哨兵位：链表第一个节点永远保持不变，并且里面数值域为空
     *
     */

    //保存整个没有（哨兵位）单链表头节点的引用
    public Node head;//引用类型默认值为NULL

    //头插法
    public void addFirst(int data) {

        //第一次插入节点(链表为空)
        if (this.head == null) {
            Node node = new Node(data);//链表头为空时（head == null），整了链表的头引用为 node
           this.head = node;
           return;
        }


        //链表不为空，单链表插入要先绑后面
        Node node = new Node(data);
        node.next = this.head;
        head = node;//把node的引用给head，然head变成新的头
    }


    //尾插
    public void addList(int data) {

        //第一次插入时
        if (this.head == null) {
            Node node = new Node(data);
            head = node;
            return;
        }


        Node node = new Node(data);
        Node cur = this.head;//cur从头开始

        /*这里注意cur不可以先走到空，如果cur走到null，那么cur的next就是cull*/
        while (cur.next != null) {
            cur = cur.next;
        }

        //出来时cur==null,就尾插
        cur.next = node;
    }


    //打印单链表
    public void display2(Node nodeH) {
        Node cur = this.head;//cur从头开始
        cur = nodeH;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void display() {
        Node cur = this.head;//cur从头开始
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }




    //查找是否包含关键字Key,是否在链表中
    public boolean contains(int key) {
        Node cur = this.head;
        while (cur != null) {
            if (cur.data == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }


    public int size() {
        Node cur = this.head;
        int count = 0;//count不能为1，如果是空链表，count=1返回就，寄了
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }

    //任意位置插入（第一个数据节点为0号下标）
    public void addIndex(int index, int data) {


        //相当于头插
        if (index == 0) {
            addFirst(data);
            return;
        }

        //相当于尾插
        if (index == this.size()) {
            addList(data);
            return;
        }

        //正常插入方法：

        /**
         *    1. 先找到index前一个节点的地址->定义一个cur走index-1步
         *    2.画图插入
         */

        //先找到index前一个节点的地址
        Node cur = searchIndex(index);

        //插入
        Node node = new Node(data);

        /**
         * 这里注意，先绑后面（node = cur.next;），因为单链表前一个节点负责，单独的维护后一个节点，前一个节点的引用被覆盖（cur节点）
         * 那么原本和cur节点连接的节点就找不到了
         */

        node.next = cur.next;
        cur.next = node;

    }


    //找到index前一个节点的地址的方法
    private Node searchIndex(int index) {
        //index下标位置检验
        if (index < 0 || index > this.size()) {
            throw new RuntimeException("下标位置不合法");
        }

        Node cur = this.head;
        while (index-1 != 0/*走index-1步*/) {
            cur = cur.next;
            index--;
        }
        return cur;//返回走index-1步后的，cur类型地址
    }


    //找key节点的前驱
    private Node searchPrev(int key) {
        Node prev = this.head;
        while(prev.next != null) {
            if (prev.next.data == key) {
                return prev;
            }else {
                prev = prev.next;//继续往后走
            }
        }
        return null;
    }


    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        /** 1. 找到，要删除节点del的前驱
         *  2. 找到要删除的节点del
         *  3. 删除节点
         */

        //空节点直接返回
        if (this.head == null) {
            return;
        }

        //头节点直接删除
        if (this.head.data == key) {
            head = head.next;
            return;//这里注意别忘记了
        }

        //1. 找到，要删除节点del的前驱
        Node prev = searchPrev(key);
        if (prev == null) {
            throw new RuntimeException("没有你要删除的节点，请考量要删除的节点");
        }

        //2. 找到要删除的节点del
        Node del = prev.next;
        //3. 删除节点
        prev.next = del.next;
    }


    //遍历单链表一遍，删除所有值为key的节点
    public void removeAllKey(int key) {
        /** 1.定义一个快指针 cur : cur指针一直往后走；
         *  2.定义一个慢指针 prev: prev指针，只有cur遇到要删除的数据时，prev指针才往后走，不然保持不动
         *  3.注意最后不要漏了，head头节点
         */

       // 1.定义一个 cur指针 : cur指针一直往后走
       //  2.定义一个 prev指针: prev指针，只有cur遇到要删除的数据时，prev指针才往后走，不然保持不动
        Node cur = this.head.next;//
        Node prev = this.head;

        while (cur != null) {
            if (cur.data == key) {
                //cur.data == key，时只有cur指针都在走，因为要遍历删除数据
                prev.next = cur.next;
                cur = cur.next;
            }else {
                //cur.data ！= key，两个指针都在动，prev指针，指向cur指针
                prev = cur;
                cur = cur.next;
            }
        }

       // 3.注意最后不要漏了，head头节点
        if (this.head.data == key) {
            this.head = this.head.next;
        }
    }


    public void clear() {
        Node cur = head;
        while (cur != null) {
            //注意定义一个，变量记住置为空的，后驱节点
           Node curN = cur.next;
           cur.next =null;//引用类型必须制空
           cur = curN;
        }

        //最后把头节点手动置为null
        head = null;
    }


    //合并两个有序链表
    public static MyLinkList.Node mergeTwoLists(Node list1, Node list2) {

        MyLinkList.Node headH = new Node(-1);
        MyLinkList.Node tmp = headH;//tmp用来遍历两个链表
        while(list1 != null && list2 != null) {
            //哪个节点数据小，就接在tmp后面
            if (list1.data < list2.data) {
                tmp.next = list1;
                list1 = list1.next;
                tmp = tmp.next;
            }else {
                tmp.next = list2;
                list2 = list2.next;
                tmp = tmp.next;
            }
        }

        //当其中一个链表遍历完，就直接接上另一个链表的后半部分
        if(list1 != null) {
            tmp.next = list1;
        }

        if(list2 != null) {
            tmp.next = list2;
        }

        return headH.next;
    }


    //链表的分割
    public Node partition(Node pHead, int x) {
        Node as = null;
        Node ae = null;
        Node bs = null;
        Node be = null;
        Node cur = pHead;

        while (cur != null) {
            if (cur.data > x) {
                //第一次插入
                if (as == null) {
                    as = ae = cur;
                }else {//第N次插入

                    ae.next = cur;
                    ae = ae.next;
                }
            } else {
                //第一次插入
                if (bs == null) {
                    bs = be = cur;
                }else{//第N次插入
                    be.next = cur;
                    be = be.next;
                }
            }

            cur = cur.next;
        }

        //当一个链表为空时，返回
        if(as == null) {
            return bs;
        }

        //如果到这里as!= null
        //连接两部分
        ae.next = bs;

        //注意，第二部分结尾不为空时，要手动把第二部分最后一个节点，手动制空
        if(bs != null) {
            be.next = null;
        }

        //最后返回as
        return bs;
    }

}
